Discuss this article in the forums.
Introduction
Straight-forward problems that don’t require a special technique
Breadth First Search (BFS)
Flood Fill<
Brute Force and Backtracking
Brute Force
Backtracking
Dynamic Programming
Hard Drills
Maximum Flow
Optimal Pair Matching
Linear Programming (Simplex)
Conclusion
With many Topcoder problems, the solutions may be found instantly just by reading their descriptions. This is possible thanks to a collection of common traits that problems with similar solutions often have. These traits serve as excellent hints for experienced problem solvers that are able to observe them. The main focus of this article is to teach the reader to be able to observe them too.
Straight-forward problems that don’t require any special technique (e.g. simulation, searching, sorting etc.)
In most cases, these problems will ask you to perform some step by step, straight-forward tasks. Their constraints are not high, and not too low. In most cases the first problems (the easiest ones) in topcoder Single Rounds Matches are of this kind. They test mostly how fast and properly you code, and not necessarily your algorithmic skills.
Most simple problems of this type are those that ask you just to execute all steps described in the statement.
Problems that use BFS usually ask to find the fewest number of steps (or the shortest path) needed to reach a certain end point (state) from the starting one. Besides this, certain ways of passing from one point to another are offered, all of them having the same cost of 1 (sometimes it may be equal to another number). Often there is given a N x M table (formed of N lines and M columns) where certain cells are passable and others are impassable, and the target of the problem is to find the shortest time/path needed to reach the end point from the start one. Such tables may represent mazes, maps, cities, and other similar things. These may be considered as classical BFS problems. Because BFS complexity is in most cases linear (sometimes quadratic, or N logN), constraints of N (or M) could be high – even up to 1 million.
Words can be considered as states. There are at most 26^4 different words composed of 4 letters (thus a linear complexity will run in allowed time).
There are some ways to pass from one state to another.
The cost of passing from a state to another is always 1 (i.e. a single button click).
You need to find the minimum number of steps required to reach the end state from start state.
Everything indicates us that it’s a problem solved by the help of a BFS. Similar things can be found in any other BFS problems. Now let’s see an interesting case of BFS problems.
Problem hints: At first sight this may seem like dynamic programming or backtracking. But as always, take a look into the text of the statement. After a while you should observe the following things:
A table is given.
The knight can jump from one cell to some of its neighbors.
The cost of passing from a cell to another is always 1 (just one jump).
You need to find the minimum number of steps (jumps).
Given this information we can see that the problem can be easily solved by the help of BFS. Don’t get confused by the fact that connected points are represented by unconnected cells. Think of cells as points in a graph, or states (whatever you want) – and in order to pass from one point to another, the knight should be able to jump from the first to the second point.
Notice again that the most revealing hint about the BFS solution is the cost of 1 for any jump.
Train yourself in finding the hints of a BFS problem in following examples:
Other example(s):
RevolvingDoors – SRM 223 Div 1.
WalkingHome – SRM 222 Div 1.
TurntableService – SRM 219 Div 1.
Flood Fill
Sometimes you may encounter problems that are solved by the help of Flood Fill, a technique that uses BFS to find all reachable points. The thing that makes them different from BFS problems described above is that a minimum path/cost is not needed.
For example, imagine a maze where 1 represents impassable cells and 0 passable cells. You need to find all cells that are reachable from the upper-left corner. The solution is very simple – take one-by-one a visited vertex, add its unvisited neighbors to the queue of visited vertices and proceed with the next one while the queue is still populated. Note that in most cases a DFS (Depth First Search) will not work for such problems due to stack overflows. Better use a BFS. For inexperienced users it may seem harder to implement, but after a little training it becomes a “piece of cake”. A good example of such problem would be:
Problem hints: What do we have here?
A map (table)
Certain points are impassable (those covered by given rectangles)
Contiguous areas need to be found
It is easy to understand that a problem with such a statement needs a Flood Fill. Usually problems using it are very easy to detect.
Brute Force and Backtracking
I have placed these 2 techniques in the same category because they are very similar. Both do the same thing – try all possible cases (situations) and choose the best one, or count only those that are needed (depending on the problem). Practically, Backtracking is just more advanced and optimized than Brute Force. It usually uses recursion and is applied to problems having low constraints (for example N<=20).
Problem hints: Well, this is one of the easiest examples. So which are the hints of this statement?
You need to find all possible situations (positions) that satisfy a certain rule (threatens all given pieces).
The limits are very low – only 8 knights are at most given.
It’s a common Brute Force problem’s statement. Note that x and y limits are not relevant, because you need only try all positions that threaten one of the knights. For each of these positions see if the knight placed at that position threatens all others too.
Another interesting problem would be:
Problem hints: And again one of the most important hints is the low limit of the size of the grid – only 50. This problem is possible to be solved with the help of the Brute Force because for each cell you can try to find the circle whose center is situated in that cell and that respects the rules. Among all of these circles found, select the one that has the greatest radius.
Complexity analysis: there are at most 50×50 cells, a circle’s radius is an integer and can be at most 25 units, and you need a linear time (depending on your implementation) for searching the cells situated on the border of the circle. Total complexity is low and thus you can apply a simple Brute Force here.
Other example(s):
Cafeteria - SRM 229 Div 1
WordFind - SRM 232 Div 1
Backtracking
This technique may be used in many types of problems. Just take a look at the limits (N, M and other main parameters). They serve as the main hint of a backtrack problem. If these are very small and you haven’t found a solution that’s easier to implement – then just don’t waste your time on searching it and implement a straight-forward backtracking solution.
Usually problems of this kind ask you to find (similarly to Brute Force):
Every possible configuration (subset) of items. These configurations should respect some given rules.
The “best” configuration (subset) that respects some given rules.
Problem hints:
First look at the constraints – there are at most ONLY 6 people! It’s enough for generating all possible permutations, sets etc.
There are different possible ways to pass the people from one side to another and you need to find the best one.
This is of course a problem solved with a backtracking: at the beginning choose any 2 people to pass the bridge first, and after that at each step try to pass any of those that have been left on the start side. From all these passages select the one that needs the smallest amount of time. Note that among persons that have passed over the bridge, the one having the greatest speed should return (it’s better than returning one having a lower speed). This fact makes the code much easier to implement. After having realized these things – just code the solution. There may be others – but you will lose more time to find another than to code this one.
Problem hints: Only 9 numbers are given at most; and every distinct way (configuration) to arrange the numbers so that they form a magic number square should be found.
These are the main properties of a Backtracking problem. If you have observed them – think about the code. You can generate all permutations of numbers and for each of them check if it forms a magic square. If so – add it to the answer. Note that it must be unique. A possible way to do that – is to have a list of earlier found configurations, thus for each new magic square check if it exists in that list and if it doesn’t – add it to the answer. There will not be many distinct magic squares, thus no additional problems will appear when applying this method.
Other example(s):
WeirdRooks - SRM 234 Div 1
Dynamic Programming
Quite a few problems are solved with the help of this technique. Knowing how to detect this type of problem can be very valuable. However in order to do so, one has to have some experience in dynamic programming. Usually a DP problem has some main integer variables (e.g. N) which are neither too small, nor too big – so that a usual DP complexity of N^2, N^3 etc. fits in time. Note that in the event that N is very small (for TC problems usually less than 30) – then it is likely the problem is not a DP one. Besides that there should exist states and one or more ways (rules) to reach one greater state from another lower one. In addition, greater states should depend only upon lower states. What is a so-called state? It’s just a certain configuration or situation. To better understand dynamic programming, you may want to read this article.
Problem hints:
Two main integer variables are given (N and S). These are neither too small, nor are they too big (i.e. a complexity of N*S fits in time).
A state can be defined as the minimum number of coins needed to reach a certain sum.
A sum (state) i depends only on lower sums (states) j (j<i).
By adding a coin to a certain sum – another greater sum is reached. This is the way to pass from one state to another.
Thus all properties of a DP problem are uncovered in this statement. Let’s see another (slightly harder) DP problem:
Problem hints:
There are N numbers given (1<=N<=50), thus N isn’t too small, nor too big.
A state (i,d) can be defined as the length of the longest zig-zag subsequence ending with the i-th number, for which the number before the last one is smaller than it for d=0, and bigger for d=1.
A state i (i.e. a subsequence ending with the i-th number) depends only on lower states j (j<i).
By adding a number to the end of a subsequence – another bigger (greater) subsequence is created. This is the way to pass from one state to another.
As you can see – this statement has almost the same traits (pattern) as in the previous problem. The most difficult part in identifying a DP problem statement is observing/seeing the states with the properties described above. Once you can do that, the next step is to construct the algorithm, which is out of the scope of this article.
Other example(s):
ChessMetric - 2003 TCCC Round 4
AvoidRoads - 2003 TCO Semifinals 4
FlowerGarden - 2004 TCCC Round 1
BadNeighbors - 2004 TCCC Round 4
Hard Drills:
Maximum Flow
In many cases it’s hard to detect a problem whose solution uses maximum flow. Often you have to create/define graphs with capacities based on the problem statement.
Here are some signs of a Maximum Flow problem:
Take a look at the constraints, they have to be appropriate for a O(N^3) or O(N^4) solution, i.e. N shouldn’t be greater than 500 in extreme cases (usually it’s less than 100).
There should be a graph with edges having capacities given, or you should be able to define/create it from data given in the statement.
You should be finding a maximum value of something.
As you can see – it’s a straight-forward maximum flow problem: water pipes represent edges of the graph, their junctions – vertices; and you have to find the maximum value of amount of water that can flow from start to end vertex in a unit of time.
Optimal Pair Matching:
These problems usually have a list of items (from a set A) for which other items (from a set B) should be assigned under some rules, so that all (or a maximum possible number of) items from set A have to each be assigned to a certain item from set B.
Mixed:
Some problems need other techniques in addition to network flows.
You are given collection of items having different costs/weights. There is a certain quantity of each item that must be achieved.
A list of sets is given. These sets are composed of some of the available items, having certain quantities of each of them. Each set has a certain cost.
The goal of the problem is to find an optimal combination (the cheapest one) of these sets so that the sum of quantities of each of the items they have is exactly the one needed to achieve.
At first it may seem confusing, but let’s see an example:
A collection of items (chemicals).
A list of sets (available mixtures), each containing certain amounts of each of the items, and having a certain cost.
You need to find the lowest price of the desired collection of items achieved by the combination of the available sets. More than that – you can take also non-integral amounts of mixtures.
These are exactly the traits described above.
Conclusion
If you have found this article interesting and you have learned new things from it – train yourself on any of the problems in the topcoder Algorithm Arena. Try hard to see the hints and determine the type of the solution by carefully reading through the problem statement. Remember, there are still many problems that may not be included properly in any of the categories described above and may need a different approach.